package me.eg.third;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 685. 冗余连接 II
 * <p>
 * 在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
 * <p>
 * 输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
 * <p>
 * 结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
 * <p>
 * 返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
 * <p>
 * 链接：https://leetcode-cn.com/problems/redundant-connection-ii
 */
public class FindRedundantDirectedConnection {
    private int n; // 节点数量
    private Map<Integer, Set<Integer>> to; // 出边数组
    private int[] inDeg; // 每个节点的入度

    public int[] findRedundantDirectedConnection(int[][] edges) {
        n = edges.length;
        inDeg = new int[n + 1];
        to = new HashMap<>();

        for (int[] edge : edges) {
            // 初始化出边数组
            Set<Integer> toP = to.getOrDefault(edge[0], new HashSet<>());
            toP.add(edge[1]);
            to.put(edge[0], toP);
            // 初始化入度数组
            inDeg[edge[1]]++;
        }

        // 每次删除一条边，判断是否合法的树
        for (int i = edges.length - 1; i >= 0; i--) {
            // 删除边，相应入度减一
            to.get(edges[i][0]).remove(edges[i][1]);
            inDeg[edges[i][1]]--;
            // 如果是合法的树，那么该边就是多余的边
            if (isValidTree()) return edges[i];
            // 还原边和入度
            to.get(edges[i][0]).add(edges[i][1]);
            inDeg[edges[i][1]]++;
        }
        return null;
    }

    private boolean isValidTree() {
        int root = 0;
        for (int i = 1; i <= n; i++) {
            if (inDeg[i] == 0) {
                if (root == 0) root = i; // 根节点的入度等于0
                else return false; // 一棵树只有一个根节点
            } else if (inDeg[i] > 1) { // 非根节点只能有一个父节点
                return false;
            }
        }

        Set<Integer> visited = new HashSet<>();
        dfs(root, visited); // 深度遍历树
        return visited.size() == n; // 判断树是否包含全部节点
    }

    private void dfs(int x, Set<Integer> visited) {
        visited.add(x);
        if (!to.containsKey(x)) return;

        for (int next : to.get(x)) {
            if (visited.contains(next)) return;
            dfs(next, visited);
        }
        return;
    }
}
